package com.swak.algs;

import com.swak.algs.array.Prints;
import com.swak.algs.array.Swaps;

/**
 * 快速排序：每次将范围内的数据分为不同的区域
 * 
 * @author lifeng
 */
public class Code17 {

	/*
	 * L ~ R 需要排序的区域
	 */
	static void process(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		int less = L - 1;
		int more = R;
		int index = L;
		while (index < more) {
			if (arr[index] < arr[R]) {
				Swaps.swap(arr, ++less, index++);
			} else if (arr[index] > arr[R]) {
				Swaps.swap(arr, index, --more);
			} else {
				index++;
			}
		}
		Swaps.swap(arr, R, more);
		process(arr, L, less);
		process(arr, more + 1, R);
	}

	public static void main(String[] args) {
		int[] arr = { 4, 2, 5, 1, 4, 7, 9, 3, 2, 4, 5 };
		Prints.print(arr);
		process(arr, 0, arr.length - 1);
		Prints.print(arr);
	}
}